1. Field of the Invention
The present invention relates to a motion vector searching apparatus, a motion vector searching method and a storage medium for storing a motion vector searching program. The present invention is applicable to, for example, a moving image (video) coding apparatus, a moving image coding method and a storage medium for storing a moving image coding program.
2. Description of the Related Art
MPEG4-AVC/H.264 (ISO/IEC 14496-10) has been known as a moving image coding technology (see “Revised Edition H. 264/AVC Text”, supervised by Sakae Okubo, jointly edited by Shinya Kadono, Yoshihiro Kikuchi and Teruhiko Suzuki, published by Impress Co., January, 2006, referred as Document 1 hereinafter).
This moving image coding technology generates a prediction block per pixel block of a frame to be coded when coding the target frame, and finds a prediction error that is a difference between the prediction block and the pixel block of the target frame to encode it.
A technology described in Japanese Patent Application National Publication (Laid-Open) No. 2006-509467 described below relates to one of this prediction image generating methods and enhances coding efficiency by focusing on changes of temporal brightness of images.
The technology described in National Publication No. 2006-509467 searches a motion vector by generating a prediction image by multiplying a reference image block by a weight, and adding an offset thereto.
After the weight and offset are determined, the prediction block is generated by multiplying the reference image block of the reference image, from which the motion vector is to be searched, by the weight with and adding the offset thereto. That is, all pixels in the prediction block Pred [x, y] are found in accordance to the following expression (1), where W is the weight, D is the offset, and ref [x, y] is the pixel data of the reference image:Pred [x, y]=ref [x+MVx, y+MVy]*W+D   (1)
In the expression (1), x and y are x and y coordinates of each pixel and MYx and MVy are x and y components of a motion vector. The operation of multiplying the weight and adding the offset as indicated in the expression (1) will be referred as “weighting” hereinafter.
Then, an inter-block difference between the obtained prediction block Pred [x, y] and a coding object block (an original block to be coded) org [x, y] is determined. The inter-block difference diff may be found in accordance to the following expression (2) for example. When the inter-block difference is smaller than a threshold value or is smaller than a previous difference, the current processing is terminated and the current candidate motion vector and weighting factor are employed.
                    diff        =                              ∑                          x              ,              y                                ⁢                      (                                                                          org                  ⁡                                      [                                          x                      ,                      y                                        ]                                                  -                                  pred                  ⁡                                      [                                          x                      ,                      y                                        ]                                                                                      )                                              (        2        )            
In the technique disclosed in National Publication No. 2006-509467, the reference image once weighted may be stored separately as the weighted reference image.
Here, the reference image for carrying out the motion vector search not only includes images having an integer number of pixels. The motion vector search may be also carried out in half pixel precision or quarter pixel precision by generating pixels at a pixel position of half pixel precision or quarter pixel precision by interpolation. This is an existing technique necessary for carrying out the motion vector search at high precision. Therefore, in such a case, a number of pixels to be searched will increase as compared to when the number of the pixels of the reference image are counted in a unit of an integer number of pixels.
FIG. 6A shows an image composed of 4×4 integer pixels and FIG. 6B shows an image in which pixels of half pixel precision are added to the image composed of the 4×4 integer pixels. The pixels of half pixel precision are disposed so as to interpolate between the integer pixels. As seen from FIGS. 6A and 6B, in case of the block of 4×4 integer pixels, the reference image may have 16 pixels in the unit of the integer number of pixels, and may have 64 pixels when the pixels are counted including the pixels of half pixel precision. The number of pixels increases more up to 256 pixels when the pixels are counted including the pixels of quarter pixel precision.
Generally, when interpolation is carried out on an image composed of n×m pixels, a number of pixels of the interpolated image including integer pixels and pixels of half pixel precision is 4×n×m pixels, which is four times greater than the case of counting only the integer pixels. When the interpolation is carried out on the image composed of n×m pixels such that a number of pixels of the interpolated image including the integer pixels and pixels of half pixel precision and quarter pixel precision will be 16×n×m pixels, the number of pixels of the interpolated image will be 16 times greater than the case of counting only the integer pixels. Assume a case when a coding object image has a size of standard TV, i.e., 720×480 pixel size. In this case, a number of pixels of the image counting integer pixels is 345,600. A number of pixels of an interpolated image including the integer pixels and pixels of half pixel precision amounts to 1,382,400, and a number of pixels of an interpolated image including the integer pixels, pixels of half pixel precision, and pixels of quarter pixel precision amounts to 5,529,600.
A concrete interpolation image generating method, in the case of H. 264 for example, is described in a section “Predictive interpolation Signal” in pp. 115 through 118 of Document 1.
The pixels of the precision finer than the integer pixel is used to enhance precision of the motion vector search and coding efficiency. Interpolated images of half pixel precision and quarter pixel precision must be taken into account as a motion vector searching range of the reference image, which are very wide. Since the conventional technique requires weighting process carried out on the reference image, the weighting process must be carried out widely on the whole pixels of the reference image, which an amount of calculations becomes enormous.
Furthermore, in the conventional technique, the weighted pixels are stored together with the normal pixels. However, because the motion vector searching range of the reference image is very wide as described above, a large memory capacity is required to store the weighted pixels. Therefore, it is difficult to implement the technology in a built-in device in which a memory area is limited.
FIG. 7 shows a relationship between the reference image and the coding object image. A block A is a coding object block (block to be coded) in the coding object image and blocks B and C are reference image blocks in the reference image. As shown in FIG. 7, one coding object block refers to the reference image blocks in the reference image by plural times. Therefore, if the weighted reference image is not stored, the weighted image must be generated many times for the reference image block. Therefore, when the weighted reference image is not stored, it takes calculation time even through a capacity for storing the weighted image becomes unnecessary.
Still more, in the motion vector search, an area outside of a screen is generally also included, as an area where edges of the screen is extended, in a searching range, and thus, in general, an area larger than the coding object image is searched.
As described above, the conventional technique takes time for calculations because the weighting process must be carried out on a large searching range and is difficult to be implemented in a built-in device or the like because it requires a large memory capacity.
Therefore, a motion vector searching apparatus, a motion vector searching method and storage medium for storing a motion vector searching program, that carry out the motion vector search in a short time without requiring a large memory capacity, are desired.